Applications using ordinary arithmetic for a calculation typically make use of algebraic transformations of the calculation to render it in a form more convenient for efficient processing. The associative law, (a+b)+c=a+(b+c), allows ordinary arithmetic calculations to be parallelized. For example, a sum, e.g., a+b+c+d+e+f+g+h+i, can be rearranged as a set of subtotals:                (a+b+c) subtotal 1        +(d+e+f) subtotal 2        +(g+h+i) subtotal 3Each subtotal can be computed in parallel, and then added together to reach the final result.        
Many digital signal processing (DSP) algorithms utilize saturating arithmetic. For example, the International Telecommunications Union-Telecommunication Standardization Section (ITU-T) G.729 Recommendation defines an algorithm for encoding voice using Conjugate-Structure Algebraic-Code-Excited Linear-Prediction (CS-ACELP). The speech coding algorithm defined in Annex E of the G.729 Recommendation utilizes saturating arithmetic.
In saturating arithmetic, the result of a single addition is restricted to a defined range. This is typically referred to as ‘saturating addition.’ Saturating addition does not obey all the algebraic laws which ordinary addition does. Specifically, saturating addition does not obey the associative law described above. That is, the additions in the sum must be performed in linear order, with saturation applied to each stage. For example, the result of the saturating addition of the sequence, a+b+c+d, can be represented as:result=sat(sat(sat(a+b)+c)+d)
The use of saturating arithmetic in G.729 as well as other DSP algorithms limits the ability to accelerate and/or improve the efficiency of these algorithms using parallel processing techniques.
What are therefore needed are systems and methods for the parallelization of saturated accumulation operations.
The present invention will now be described with reference to the accompanying drawings. In the drawings, like reference numbers can indicate identical or functionally similar elements. Additionally, the left-most digit(s) of a reference number may identify the drawing in which the reference number first appears.